//
// Created by francklinson on 2021/7/19 AT 23:11.
//
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>> &edges) {
        if (n == 1) return {0};
        vector<int> degree(n, 0);
        vector<vector<int>> neighbor(n, vector<int>());
        for (auto &edge : edges) {
            ++degree[edge[0]];
            ++degree[edge[1]];
            neighbor[edge[0]].push_back(edge[1]);
            neighbor[edge[1]].push_back(edge[0]);
        }
        queue<int> q;
        for (int i = 0; i < n; ++i) {
            // 入度为1的入队
            if (degree[i] == 1)
                q.push(i);
        }
        vector<int> ans; // 放答案
        while (!q.empty()) {
            ans = {};
            auto levelSize = q.size();
            for (int i = 0; i < levelSize; ++i) {
                auto p = q.front();
                q.pop();
                ans.push_back(p);
                for (auto &x:neighbor[p]) {
                    if (--degree[x] == 1) // 去掉叶节点 对应的邻节点入度-1  如果此时邻节点成为新的叶节点 则入队
                        q.push(x);
                }
            }
        }
        return ans;
    }
};

int main() {
    vector<vector<int>> edges{{1, 0},
                              {1, 2},
                              {1, 3}};
    vector<vector<int>> edges2{
            {3, 0},
            {3, 1},
            {3, 2},
            {3, 4},
            {5, 4}
    };
    vector<vector<int>> edge3{{0, 1},
                              {0, 2}};
    Solution solution;
    auto ans = solution.findMinHeightTrees(6, edges2);
    for (auto &x:ans) cout << x << endl;
    ans = solution.findMinHeightTrees(3, edge3);
    for (auto &x:ans) cout << x << endl;
    return 0;
}

